package BinarySearchTree;

public class BinarySearchTree {
    static class TreeNode{
        TreeNode left;
        TreeNode right;
        int val;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    TreeNode root;

    public boolean search(int key){
        TreeNode cur=root;
        // 找位置
        while(cur!=null){
            if(cur.val > key){
                cur=cur.left;
            }else if(cur.val < key){
                cur=cur.right;
            }else{
                return true;
            }
        }
        return false;
    }

    public boolean insert(int key){
        if(root==null){
            root=new TreeNode(key);
            return true;
        }
         TreeNode cur=root;
         TreeNode parent=null;
         TreeNode node=new TreeNode(key);
         // 找位置
         while(cur!=null){
             if(cur.val > key){
                 parent=cur;
                 cur=cur.left;
             }else if(cur.val < key){
                 parent=cur;
                 cur=cur.right;
             }else{
                 return false;
             }
         }
         if(parent.val>key){
             parent.left=node;
         }else{
             parent.right=node;
         }
         return true;
    }

    public  void delete(int key){
        TreeNode cur=root;
        TreeNode parent=null;
        // 找位置
        while(cur!=null){
            if(cur.val > key){
                parent=cur;
                cur=cur.left;
            }else if(cur.val < key){
                parent=cur;
                cur=cur.right;
            }else{
                //开始删除
                removeNode(cur,parent);
                break;
            }
        }
    }

    private void removeNode(TreeNode cur, TreeNode parent) {

        if (cur.left == null) {
            if (cur == root) {
                root = cur.right;
            }
            if (parent.left == cur) {
                parent.left = cur.right;
            } else {
                parent.right = cur.right;
            }
        } else if (cur.right == null) {
            if (cur == root) {
                root = cur.left;
            }
            if (parent.left == cur) {
                parent.left = cur.left;
            } else {
                parent.right = cur.left;
            }
        } else {
            TreeNode curNode = cur;
            TreeNode node = cur.right;
            // 当左右都存在节点时，可以找右子树的最左边的节点--最小值
            while (node.left != null) {
                curNode = node;
                node = node.left;
            }
            // node 就是 右子树最小节点
            cur.val = node.val;

            if (curNode.left == node) {
                curNode.left = node.right;
            } else {
                curNode.right = node.right;
            }
        }
    }
}
